package leetcode.code;

import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution921 implements IDebug {

	public int minAddToMakeValid(String s) {
		int left = 0;
		int ans = 0;
		for (char c : s.toCharArray()) {
			if (c == '(') {
				left++;
			} else if (c == ')' && left > 0) {
				left--;
			} else {
				ans++;
			}
		}
		return ans + left;
	}

	public int minAddToMakeValid1(String s) {
		Stack<Character> stack = new Stack<>();
		for (char c : s.toCharArray()) {
			if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
				stack.pop();
			} else {
				stack.add(c);
			}
		}
		return stack.size();
	}

	@Override
	public void debug1() {
		String s = "())";
		int e = 1;
		int r = this.minAddToMakeValid(s);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution921 so = new Solution921();
		so.debug1();

	}

}
